This invention relates to sequential circuits and more particularly to the process of testing sequential circuits.
A synchronous sequential circuit can always be represented in the canonical form shown in FIG. 1. It comprises a combinational portion 10 that is fed by primary inputs x and by state variables y. Variables y are provided by the outputs of the clocked flip-flops that form the memory portion 20 of the FIG. 1 circuit. Combinational portion 10 provides feedback outputs Y that are applied to portion 20 and primary outputs Z that form the outputs of the FIG. 1 circuit. The various states that the flip-flops in portion 20 can assume form the set of states of the FIG. 1 circuit. Stated in other words, every state of the FIG. 1 circuit corresponds to a different combination of values of the state variables, y. The FIG. 1 circuit changes state only when it receives a pulse on the clock line of portion 20 which allows the flip-flops to change state. Although a sequential circuit may have several different clocks, the following discusses the case of only one clock signal, but as will be clearly apparent hereinafter, this invention is applicable to circuits with any number of clocks.
In the classical method for testing sequential circuits, a sequence of test vectors is applied to the circuit while the circuits outputs are observed. Each vector is a set of bits which correspond in number to the number of primary inputs, x. The specific procedure is to apply a test vector to the inputs, supply a clock signal to the circuit, observe the outputs Z, supply the next vector, and repeat the process. With each application of the clock signal, the circuit is made to enter the state dictated by the inputs, Y, to portion 20.
By carefully selecting the sequence of test vectors, a large proportion of the possible fault effects in the sequential circuit (perhaps even all) can be made to appear at the primary outputs of the circuit under test and, thus, be observed and detected.
For test generation, i.e., for the process that generates the sequence of test vectors, the synchronous sequential circuit of FIG. 1 can be modeled by a pseudo-combinational iterative array of FIG. 2. Basically, this modeling technique maps the time domain response of the sequential circuit into a space domain response of the iterative array, and allows test generation methods developed for combinational circuits to be extended to synchronous sequential circuits. In FIG. 2, x(0) is the first applied vector, y(0) is the state of the circuit at the time x(0) is applied, Y(0) is the output of portion 10 that is applied to flip flops 20, y(1) is the output of the flip-flops that are responsive to input Y(0), etc. The FIG. 2 model is equivalent to the FIG. 1 model because each cell C(i) of the array is identical to the combinational circuit portion 10 of FIG. 1. In this transformation, the clocked flip-flops are modeled as combinational elements, and thus they may be more correctly referred to as pseudo-flip-flops. The pseudo-flip-flops have direct connections from input to output.
The test generation problem for sequential circuits is very complex because the search for a solution involves multiple time frames, as demonstrated by the FIG. 2 model. In the presence of cycles, i.e., flip-flops forming circular loop structures, the worst-case complexity of a sequential test generation algorithm is an exponential function of the number of flip-flops in the circuit. Many approaches have been reported in the literature that employ different variations of the classical techniques. By way of example, U.S. application Ser. No. 07/497,824 filed Mar. 22, 1990, entitled "A Cost-directed Search Method for Generating Test for Sequential Logic Circuits" describes one such variation.
While these approaches all attempt to speed up the testing process, a basic problem remains which is associated with the fact that each application of a test vector is accompanied with the application of a clock. Usually, the current state is a necessary condition for detecting a set of fault effects F. However, because the prior art applies only one vector in the current state, only a subset of F can be detected. Sometimes, that subset is extremely small, and that results is a very long test sequence.
This phenomenon may best be illustrated, perhaps, with a circuit that is driven by a counter. FIG. 3, for example, contains a three stage simple binary counter that, on consecutive applications of the clock, advances through states 000, 001,010, 011, 100, 101, 110, 111 in sequence. The combinational circuitry in FIG. 3 develops an output S=0 only when the counter is in state 111. To fully test OR gate 30, one needs to apply the combinations (A=0, S=0), (A=1, S=0), and (A=0, S=1). Thus, both combinations that require S=0 also require the counter to be in state 111. But in the classical approach, when the counter is in state 111 and one vector is applied, say A=1, followed by activation of the clock, the counter goes into state 000. Then, to be able to apply the combination (A=0, S=0) to the OR gate, the counter must be brought again into the desired state 111, which means that the entire cycle of 8 states must be traversed.
This type of operation is obviously less than optimal, since a circuit may have to be cycled through many states for the sole purpose of reaching a previously reached state, only to allow the application of another vector. Such recycling may need to be carried out a number of times, and that is clearly inefficient. This deficiency is inherent in the classical mode of testing sequential circuits and is independent of the method used for generating test sequences.